A. Field of the Invention
The invention relates generally to scheduling of packets and/or cells in an input buffered switch, and, more particularly, to a packet and cell switching apparatus method using parallel switching units. Switching performance is improved by increasing the number of scheduled packets and/or cells per time period in a switching system using parallel switching units.
B. Description of the Related Art
With respect to the design of large-scale packet switches and routers, it is well known in the art that a pure output buffering strategy, while providing high switching efficiency, is not scalable as switch dimensions get larger. This is mainly due to the requirement that the switch core operates faster than the individual switch ports by a factor equivalent to the number of ports. For this reason, large capacity switches are generally of the “input buffered” variety, with the input and output port modules being interconnected via switch units such as crossbars. To overcome the input buffer head-of-line (HOL) blocking phenomenon, the buffer at each input port is organized into a set of input queues, and each input queue is dedicated for packets destined to a particular output port.
A general input queued switch has N input ports and M output ports, whereby N and M are integer values, in which each input port uses an input queue per output port, and whereby there are therefore N×M input queues in total. A scheduler identifies a set of matching input/output pairs between which packets or cells are transmitted via switch units without conflict. The throughput efficiency of this switch depends on the efficiency of the scheduling algorithm. For this reason, a variety of scheduling algorithms based on various forms of sub-optimal heuristics are currently employed in the industry.
Three widely known heuristic algorithms for scheduling traffic in input-queued switches are: Parallel Iterative Matching (PIM), Round-Robin Matching (RRM) and iSLIP. Each of these algorithms tries to maximize the matching efficiency by attempting to pick conflict free sets of inputs/output pairs, and, typically, multiple successive iterations are performed to improve the matching efficiency.
The PIM method consists of three steps: request, grant, and accept. At the request step, N×M input queues send requests to output ports. At the grant step, each output port randomly grants a request among received requests and notifies the result to each input port. An input port may receive a number of grants from output ports, but accepts only one randomly selected grant. Thus, the PIM method operates by randomly selecting a candidate input for each output port in a first output arbitration (grant step) phase. Then, in a second input arbitration (accept step) phase, the system resolves conflicts among the plurality of outputs that may be selected for each input, by employing a similar randomization strategy.
The RRM method achieves the same goals in a similar sequence of output and input arbitration phases as with the PIM method, except that the selections are made in a deterministic fashion using a round-robin arbitration pointer implemented at each output and input port.
The iSLIP method operates in a way similar to RRM, except that the movement of the output and input round-robin pointers is conditioned on successful matches, whereas it is unconditional in the case of RRM. The typical iSLIP method is described in detail in U.S. Pat. No. 5,500,858, issued to Nicholas McKeown.
In conventional switch devices, resource arbitration must be addressed. One such conventional resource arbitration method is described in detail in U.S. Pat. No. 5,267,235, issued to Charles Thacker, whereby a rapid one-to-one match between requesters and servers is performed, whereby each server selects one request, preferably in a random manner.
Another scheduling algorithm is described in U.S. Pat. No. 6,633,568, issued to Man Soo Han et al., whereby a two-dimensional round-robin scheduling algorithm is described, in which multiple selections are made in an input-buffered switch.
Yet another scheduling algorithm is described in U.S. Pat. No. 6,813,274, issued to Hiroshi Suzuki et al., which attempts to solve a problem with conventional scheduling method of only allowing one accept per input port, by allowing for multiple accepts per inputs.
For each of these conventional scheduling algorithms, a synchronization problem exists when a number of output ports generate a grant for an identical input port. These algorithms attempt to maximize the matching efficiency by performing multiple successive iterations, and in the worst case, the algorithm must be repeated N times to converge for an N×M switch. Furthermore, these multiple iterations decrease the switching performance in terms of scheduling decisions per time unit.
The present invention is directed to overcoming or at least reducing the effects of one or more of the problems set forth above.